package org.example.node;

import org.example.BalancePlusTree;
import org.example.bo.SearchResultBO;

import java.util.List;

import static org.example.enums.SearchResultEnum.FOUND;
import static org.example.enums.SearchResultEnum.NOT_FOUND;

/**
 * @author lik
 */
public abstract class AbstractNode<K extends Comparable<K>, V> {

    /**
     * B-Tree 每个节点的度（千万一定记住要小于2哦）
     */
    protected static final int DEGREE = 4;

    /**
     * 删除操作后，为了保持树的有效性，设置最小数据度
     */
    protected static final int MINIMUM_VALUE = DEGREE / 2;

    /**
     * 查询
     *
     * @param key key
     * @return V
     */
    public abstract V query(K key);

    /**
     * 删除
     *
     * @param key key
     */
    public abstract void delete(K key);

    /**
     * 设置父节点
     *
     * @param parent parent
     */
    public abstract void setParent(AbstractNode<K, V> parent);

    /**
     * 插入数据
     *
     * @param key             key
     * @param value           value
     * @param balancePlusTree B+树
     */
    public abstract void insertOrUpdate(K key, V value, BalancePlusTree<K, V> balancePlusTree);

    /**
     * 获取最小值
     *
     * @return 最小值
     */
    public abstract K getMinimumKey();

    public static <K extends Comparable<K>> SearchResultBO commonBinarySearch(List<K> list, K key) {
        return commonBinarySearch(list, key, false);
    }

    /**
     * 二分查找
     *
     * @param list list
     * @param key  key
     * @param needFix 是否需要修正位置
     * @return 关键字位置
     */
    public static <K extends Comparable<K>> SearchResultBO commonBinarySearch(List<K> list, K key, boolean needFix) {
        int low = 0;
        int high = list.size() - 1;
        // 定义中位
        int middle;

        if (list.get(low).compareTo(key) > 0) {
            return SearchResultBO.create(NOT_FOUND, 0);
        }
        if (list.get(high).compareTo(key) < 0) {
            return SearchResultBO.create(NOT_FOUND, list.size());
        }

        while (low <= high) {
            middle = (low + high) / 2;
            if (list.get(middle).compareTo(key) > 0) {
                //比关键字大则关键字在左区域
                high = middle - 1;
            } else if (list.get(middle).compareTo(key) < 0) {
                //比关键字小则关键字在右区域
                low = middle + 1;
            } else {
                return SearchResultBO.create(FOUND, middle);
            }
        }
        if (needFix) {
            return SearchResultBO.create(NOT_FOUND, Math.max(low - 1, 0));
        }
        //最后仍然没有找到，则返回
        return SearchResultBO.create(NOT_FOUND, low);
    }

}
